package leetcode.editor.cn.dsa19_trie;
//请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
//
// 实现词典类 WordDictionary ： 
// WordDictionary() 初始化词典对象
// void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配 
// bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '
//.' ，每个 . 都可以表示任何一个字母。 
//
// 示例： 
//输入：
//["WordDictionary","addWord","addWord","addWord","search","search","search","se
//arch"]
//[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
//输出：
//[null,null,null,null,false,true,true,true]
//
//解释：
//WordDictionary wordDictionary = new WordDictionary();
//wordDictionary.addWord("bad");
//wordDictionary.addWord("dad");
//wordDictionary.addWord("mad");
//wordDictionary.search("pad"); // return False
//wordDictionary.search("bad"); // return True
//wordDictionary.search(".ad"); // return True
//wordDictionary.search("b.."); // return True
// 
// 提示：
// 1 <= word.length <= 500
// addWord 中的 word 由小写英文字母组成 
// search 中的 word 由 '.' 或小写英文字母组成 
// 最调用多 50000 次 addWord 和 search 
// 
// Related Topics 设计 字典树 回溯算法 
// 👍 193 👎 0


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class DesignAddAndSearchWordsDataStructure211 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class WordDictionary {
        Map<Integer, ArrayList<String>> wordMap;
        /**
         * Initialize your data structure here.
         */
        public WordDictionary() {
            wordMap = new HashMap<>();
        }

        /**
         * Adds a word into the data structure.
         */
        public void addWord(String word) {
            // 存储单词长度与单词列表的映射
            wordMap.computeIfAbsent(word.length(), x -> new ArrayList<>()).add(word);
        }

        /**
         * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
         */
        public boolean search(String word) {
            int len = word.length();
            if (!wordMap.containsKey(len)) return false; // 先判断单词长度
            int pointCount = 0; // 计算点的个数
            for (int i = 0; i < len; i++) {
                if (word.charAt(i) == '.') pointCount++;
            }
            for (String str : wordMap.get(len)) {
                // 如果某个单词与搜索目标字符差和点的个数相同，则返回true
                if (countWordDiff(str, word, pointCount)) return true;
            }
            return false;
        }

        private boolean countWordDiff(String word1, String word2, int count) {
            int diffCount = 0;
            for (int i = 0; i < word1.length(); i++) {
                if (word1.charAt(i) != word2.charAt(i)) {
                    if (++diffCount > count) return false;
                }
            }
            return diffCount == count;
        }
    }
    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.addWord(word);
     * boolean param_2 = obj.search(word);
     */
    //leetcode submit region end(Prohibit modification and deletion)
}